// https://leetcode.cn/problems/count-complete-tree-nodes/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 利用完全二叉树性质进行高效节点计数
// 2. 分别计算左右子树深度判断最后一层节点分布
// 3. 如果右子树深度等于左子树深度-1，说明左子树是满二叉树
// 4. 如果右子树深度小于左子树深度-1，说明右子树是满二叉树
// 5. 递归计算非满二叉树部分的节点数
// 6. 时间复杂度：O(log²N)，空间复杂度：O(logN)（递归栈深度）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "BinaryTreeUtils.h"

class Solution 
{
private:
    int GetDepth(TreeNode* root)
    {
        int Depth = 0;
        while (root != nullptr)
        {
            Depth++;
            root = root->left;
        }
        return Depth;
    }
public:
    int countNodes(TreeNode* root) 
    {
        if (root == nullptr) return 0;

        int height = GetDepth(root);
        int rightHeight = GetDepth(root->right);

        if (rightHeight == height - 1)
        {
            return ((1 << (height - 1)) - 1) + 1 + countNodes(root->right);
        }
        else
        {
            return countNodes(root->left) + 1 + ((1 << rightHeight) - 1);
        }
    }
};

int main()
{
    vector<string> nodes1 = {"1","2","3","4","5","6"};
    vector<string> nodes2 = {"1"};

    Solution sol;

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    cout << sol.countNodes(root1) << endl;
    cout << sol.countNodes(root2) << endl;

    return 0;
}